The present invention relates generally to event simulation. More particularly, the present invention relates to maintaining and managing an event queue comprising multiple events.
Before a new electronic circuit design is put into mass production, it must be tested. One way to test the design is to fabricate a device according to the design, and then to test the device. However, this approach consumes significant time, effort and money. Consequently, it has become increasingly popular to simulate the circuit in software before fabricating a device. A similar approach is taken with regard to design of networks and other complex systems.
Such a simulation is generally arranged as a time-ordered collection of discrete events, referred to as an “event queue.” Each event in the event queue represents a change in the simulated system, such as a change in the state of a signal within a circuit. During the simulation, events can be added to the event queue to represent further changes within the system. Once the simulation time reaches the event time that was set for a particular event, and the simulation software executes the changes resulting from this event, the event is removed from the event queue.
Event queues are commonly simulated by creating data structures that are operated upon by software running on a computer. One conventional implementation, the “common event queue” commonly used in open-source kernels, is implemented as a linked list of items, ordered by time, where each item represents an event in the event queue. Advantages of the common event queue include simplicity and rapid removal of events from the event queue. However, a significant disadvantage of the common event queue is slow insertion of new events into the event queue.